package com.example.shirotest.study;

import java.util.ArrayList;

//查找算法
public class SearchTest {

    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i;
        }

        ArrayList<Integer> str = binarySearch(arr, 0, arr.length - 1, 5);
        //System.out.println(str);

        //int i = insertValueSearch(arr, 0, arr.length - 1, 6);
        //System.out.println("The index is : "+i);

    }

    //顺序查找（线性查找）
    public static int orderSearch(int[] arr,int value){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == value){
                return i;
            }
        }
        return -1;
    }


    //二分查找/折半查找
    /**
     * @param arr     数组，必须是有序的
     * @param left    左侧值的索引
     * @param right   右侧值的索引
     * @param findVal 需要查找的内容
     * @return
     */
    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal){
        System.out.println("binarySearch~~");

        //当前left > right 时，说明递归整个数组，但是没有找到
        if (left > right){
            return null;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if(findVal > midVal){  //向右递归
            return binarySearch(arr,mid+1,right,findVal);
        } else if (findVal < midVal) {
            return binarySearch(arr,left,mid-1,findVal);
        }else {
            //return mid;

            //如果有多个值的情况下，需要全部返回
            ArrayList<Integer> resIndexList = new ArrayList<>();
            int temp = mid - 1;
            while (true){
                if(temp < 0 || arr[temp] != findVal){
                    break;
                }

                resIndexList.add(temp);
                temp--;
            }

            resIndexList.add(mid);

            temp = mid + 1;
            while (true){
                if(temp > arr.length-1 || arr[temp] != findVal){
                    break;
                }

                resIndexList.add(temp);
                temp++;
            }

            return resIndexList;
        }
    }

    //插值查找
    /**
     * @param arr     数组，必须是有序的。对于连续（分布均匀）且数据量大的集合来说，效果更明细
     * @param left    左侧值的索引
     * @param right   右侧值的索引
     * @param findVal 需要查找的内容
     * @return
     */
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        System.out.println("insertValue~~");

        //注意：findVal < arr[0] || findVal > arr[arr.length-1] 必须要
        //否则得到的 mid 可能越界
        if(left > right || findVal < arr[0] || findVal > arr[arr.length-1]){
            return -1;
        }

        //求出mid,自适应
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if(findVal > midVal){   //向右递归
            return insertValueSearch(arr,mid+1,right,findVal);
        } else if (findVal < midVal) {  //向做递归
            return insertValueSearch(arr,left,mid-1,findVal);
        }else {
            return mid;
        }
    }



    //斐波那契查找


}
